// Author: Domien Nowicki

#include "MapBacktrack.h"
#include <algorithm>
using namespace std;

MapBacktrack::MapBacktrack(const Map& map, const Properties& properties): MapSolver(map, properties)
{
	originalMap = &map;
}

MapBacktrack::~MapBacktrack()
{
}

void MapBacktrack::ClearHistory()
{
	// Clear the history stack
	while( !history.empty())
	{
		history.pop();
	}
}

unsigned int MapBacktrack::ColorToIndex(const Color& color)
{
	unsigned int result = -1;

	// Convert a color to an index via the properties
	for(unsigned int i=0; i<properties.GetColorCount(); i++)
	{
		// If a match is found, then we have its index
		if (properties.GetColor(i) == color)
		{
			result = i;

			break;
		}
	}

	return result;
}

// Convert an index to a color
Color MapBacktrack::IndexToColor(const unsigned int index)
{
	// Incase of invalid index, return an empty color
	if (-1 == index)
	{
		Color eraseColor;

		return eraseColor;
	}
	else
	{
		// Return the color according to the properties
		return properties.GetColor(index);
	}
}


// Initialize the backtracking algorithm
// (the map may not be externally modified after this call, or if it was modified, call Initialize again)
void MapBacktrack::Initialize()
{
	std::list<Land*>::iterator landIt;
	std::list<Province*>::iterator provinceIt;

	// Clear history
	ClearHistory();


	// Iterate through the map looking for colored provinces
	for(landIt = map.GetLands().begin(); landIt != map.GetLands().end(); ++landIt)
	{
		Land* land = *landIt;

		for(provinceIt = land->GetProvinces().begin(); provinceIt != land->GetProvinces().end(); ++provinceIt)
		{
			Province* province = *provinceIt;

			Color provinceColor = province->GetColor();

			// If colored province found, add it to the history stack
			if (provinceColor.IsColor())
			{
				PushInitialHistory(provinceColor, land, province);
			}
		}
	}
}

// Push a history step on the stack
void MapBacktrack::PushInitialHistory(const Color& color, Land* land, Province* province)
{
	struct HistoryStep step;
	unsigned int index = ColorToIndex(color);

	
	// A history step consists of a tested bitmask (shows which colors have been tried already),
	//  a nexttry (what color test to try next), and the province's land and province pointers

	step.tested = (1<<index);
	step.nexttry = index;

	step.land = land;
	step.province = province;

	history.push(step);
}

// Undo provinces which has neighbours with the same color
bool MapBacktrack::UndoDoubles(Move *move)
{
	std::list<Land*>::iterator landIt;
	std::list<Province*>::iterator provinceIt;


	// Iterate through the map
	for(landIt = map.GetLands().begin(); landIt != map.GetLands().end(); ++landIt)
	{
		Land* land = *landIt;

		for(provinceIt = land->GetProvinces().begin(); provinceIt != land->GetProvinces().end(); ++provinceIt)
		{
			Province* province = *provinceIt;

			Color provinceColor = province->GetColor();

			// If province has a color, and its neighbour contains the same color
			if (provinceColor.IsColor() && province->NeighbourContainsColor( provinceColor ))
			{
				Color eraseColor;

				// Erase it
				*move = Move(&map, land->GetName(), province->GetName(), eraseColor);

				DoMove(move);

				// Re-initialize the backtrack algorithm
				Initialize();
				
				return true;
			}
		}
	}

	// No doubles found
	return false;
}

bool MapBacktrack::CanColor(Province *province, Color *availableColor)
{
	bool result = false;


	// Check if any of the available colors are possible on this province
	for(unsigned int i=0; i < GetProperties().GetColorCount(); i++)
	{
		Color color = GetProperties().GetColor(i);

		// Check if a neighbour does not already contain this test color
		if (!province->NeighbourContainsColor(color))
		{
			*availableColor = color;
			result = true;

			break;
		}
	}

	return result;
}


// Randomly fill a province which is not colored yet (if possible)
bool MapBacktrack::FillMove(Move *move)
{
	std::list<Land*>::iterator landIt;
	std::list<Province*>::iterator provinceIt;

	Land *landMostNeighbours = 0;
	Province *provinceMostNeighbours = 0;
	unsigned int neighbourCount;
	Color colorMostNeighbours;
	Color color;

	// Iterate through the map
	for(landIt = map.GetLands().begin(); landIt != map.GetLands().end(); ++landIt)
	{
		Land* land = *landIt;

		for(provinceIt = land->GetProvinces().begin(); provinceIt != land->GetProvinces().end(); ++provinceIt)
		{
			Province* province = *provinceIt;

			// If province has not been colored yet
			if (province->GetColor().IsColor())
				continue;

			if (!CanColor(province, &color))
				return false;

			if (0 == provinceMostNeighbours || province->NeighbourColoredCount() >= neighbourCount)
			{
				landMostNeighbours = land;
				provinceMostNeighbours = province;
				colorMostNeighbours = color;
				neighbourCount = province->NeighbourColoredCount();
			}
		}
	}
	// So color this province
	*move = Move(&map, landMostNeighbours->GetName(), provinceMostNeighbours->GetName(), colorMostNeighbours);
	DoMove(move);

	// Add a history of this color for this province to the stack
	PushInitialHistory(colorMostNeighbours, landMostNeighbours, provinceMostNeighbours);
	return true;
}




// Do the move to the backtrack map
void MapBacktrack::DoMove(const Move* move)
{
	map.SetColor(move->GetLand(), move->GetProvince(), move->GetColor());
}

// Find an color (index) which has not been tested yet
int MapBacktrack::FindUntestedIndex(unsigned int tested, Province *province)
{
	// Default return value when no more colors can be tested for this province
	int result = -1;

	// Iterate through all available colors
	for(unsigned int i=0; i<properties.GetColorCount(); i++)
	{
		// If index i has not been tested yet, and a province's neighbour does not contain color i yet
		if (0 == (tested & (1<<i)) && !province->NeighbourContainsColor(IndexToColor(i)))
		{
			// Then this is the next color index to test
			result = i;
			break;
		}
	}

	return result;
}

// Pop last history step from the stack
void MapBacktrack::PopHistoryStep()
{
	history.pop();

	// We should not have to pop the first entry of the stack, that would mean the problem is unsolvable, which it should not
	if (history.empty())
		throw "Backtrack error";
}

// Modify last step on the stack to show that we are testing a new color
void MapBacktrack::NextTest(int index)
{
	// Get top
	struct HistoryStep step = history.top();

	// Pop the top
	history.pop();

	// Add it to the tested list
	if (-1 != index)
	{
		step.tested |= 1<<index;
	}

	// And show which color index we are testing
	step.nexttry = index;

	// And push it back
	history.push(step);
}

// Get the next untested index for the last step of the history stack
int MapBacktrack::NextUntestedIndex()
{
	struct HistoryStep step = history.top();

	int untestedIndex = FindUntestedIndex(step.tested, step.province);

	return untestedIndex;
}

// Erase a color in hope to find a better one next
void MapBacktrack::EraseMove(Move *move)
{
	int untestedIndex;
	// the previous step (parent) will need to get erased in any case
	struct HistoryStep parentStep = history.top();

	// Check if the next test color of the parent province is exhausted
	untestedIndex = NextUntestedIndex();

	if (-1 == untestedIndex)
	{
		// Drop the parent, and calculate the next test color for the parent's parent
		PopHistoryStep();

		untestedIndex = NextUntestedIndex();
	}

	// Show which color we will be testing
	NextTest(untestedIndex);

	Color eraseColor;

	// Before we can color a province, we must erase it first
	*move = Move(&map, parentStep.land->GetName(), parentStep.province->GetName(), eraseColor);

	// Change the backtrack's map aswell
	DoMove(move);
}

// Do finishing work for the previous steps on the stack
bool MapBacktrack::FinishLastMove(Move *move)
{
	bool result = false;
	struct HistoryStep step = history.top();

	// If the step's next try is -1, then we must erase this step's corresponding province, and prepare the next step
	if (step.nexttry == -1)
	{
		// Drop this province
		PopHistoryStep();

		// And prepare the next test
		NextTest( NextUntestedIndex() );

		Color eraseColor;

		// Erase this province's color
		*move = Move(&map, step.land->GetName(), step.province->GetName(), eraseColor);

		result = true;
	}	
	else
	{
		Color nextTryColor = IndexToColor(step.nexttry);

		// Else if we need to change the corresponding province to a new color (check if stack history and real map don't match)
		if (nextTryColor != step.province->GetColor())
		{
			const std::string& landName = step.land->GetName();
			const std::string& provinceName = step.province->GetName();

			// Erase color if needed, otherwise return the next try's color
			*move = Move(&map, landName, provinceName, EraseColored(step.province->GetColor(), nextTryColor));

			result = true;
		}
	}

	// If successful, change the backtrack's map aswell
	if (result)
		DoMove(move);

	return result;
}


Move MapBacktrack::NextMove()
{
	Move m;

	// Undo provinces which have neighbours containing the same color
	if (UndoDoubles(&m))
	{
		return m;
	}

	// React to special case where previous erase caused an erase-chain-reaction,
	//  or previous color was erased, so we can place a new color now
	if (!history.empty() && FinishLastMove(&m))
	{
		return m;
	}
	
	// Randomly fill an province in the map
	if (FillMove(&m))
	{
		return m;
	}

	// We're stuck.. try to erase a province
	EraseMove(&m);

	return m;
}

Color MapBacktrack::EraseColored(const Color& orgColor, const Color& newColor)
{
	if (orgColor.IsColor())
	{
		Color eraseColor;
		return eraseColor;
	}
	else
	{
		return newColor;
	}
}

// Try to find the next hint move by doing mismatch tests
bool MapBacktrack::MismatchMove(bool eraseFirst, Move *move)
{
	std::list<Land*>::iterator landIt;
	std::list<Province*>::iterator provinceIt;

	// Iterate through the solved map 
	for(landIt = map.GetLands().begin(); landIt != map.GetLands().end(); ++landIt)
	{
		Land *land = *landIt;

		for(provinceIt = land->GetProvinces().begin(); provinceIt != land->GetProvinces().end(); ++provinceIt)
		{
			Province *province = *provinceIt;

			const std::string& landName = land->GetName();
			const std::string& provinceName = province->GetName();

			// Get corresponding land/province of the original map 
			const Land* orgLand = originalMap->GetLand(landName);
			const Province* orgProvince = orgLand->GetProvince(provinceName);

			Color orgColor = orgProvince->GetColor();
			Color newColor = province->GetColor();

			// We want to inspect a province with a different color than in the new solved map
			if (newColor == orgColor)
				continue;

			// If we are required to erase all colored mismatches first, or if we must just fill mismatches (no erase required)
			if ((eraseFirst && orgColor.IsColor()) || (!eraseFirst))
			{
				// if erase required
				newColor = EraseColored(orgColor, newColor);

				// return hint move
				*move = Move(&map, landName, provinceName, newColor);
				return true;
			}
		}
	}

	return false;
}

Move MapBacktrack::HintMove()
{
	Move m;

	// Initialize backtracking
	Initialize();

	// Find a solution to the map
	while(!map.IsCompleted())
	{
		Move move = NextMove();

		DoMove(&move);
	}

	// Erase all mismatches with a colored province first
	if (MismatchMove(true, &m))
	{
		return m;
	}
	else
	{
		// Then start filling up the mismatches (no erasing required)
		MismatchMove(false, &m);

		return m;
	}
}



